For the design of digital circuits on the scale of VLSI (very large scale integration) technology, designers often employ computer aided techniques. Standard languages such as Hardware Description Languages (HDLs) have been developed to describe digital circuits to aid in the design and simulation of complex digital circuits. Several hardware description languages, such as VHDL and Verilog, have evolved as industry standards. VHDL and Verilog are general purpose hardware description languages that allow definition of a hardware model at the chip primitive level, the register transfer level (RTL) or the behavioral level using abstract data types. As device technology continues to advance, various product design tools have been developed to adapt HDLs for use with newer devices and design styles.
In designing an integrated circuit with an HDL code, the code is first written and then compiled by an HDL compiler. The HDL source code describes at some level the circuit elements, and the compiler produces an RTL netlist from this compilation. An RTL netlist is composed of a plurality of RTL objects, or components, and a plurality of nets which are the signal connections between the components. The RTL netlist can be a technology independent netlist in that it is independent of the technology or architecture of a specific vendor's integrated circuit, such as field programmable gate arrays (FPGA) or an application-specific integrated circuit (ASIC). The RTL netlist corresponds to a schematic representation of circuit elements (as opposed to a behavioral representation). A mapping operation is then performed to convert from the technology independent RTL netlist to a technology specific netlist which can be used to create circuits in the vendor's technology or architecture, including placing the instances and routing the interconnections so that the circuit meets given timing, space and power constraints.
Early electronic design automation (EDA) totally separates the HDL synthesis from the placement/routing processes as shown in FIG. 1. In operation 11, HDL code is prepared. In operation 13, the HDL prepared in operation 11 is compiled and synthesized to produce a netlist which is typically optimized by performing logic optimization. Thereafter, a mapping process maps the netlist to a specific target technology/architecture. At the end of operation 13, the synthesis has been completed and a netlist which is specific to the technology/architecture used in the vendor's IC is now provided. This netlist is effectively at a gate level with timing analysis estimated by using statistical models of the interconnect properties based on pre-placement information such as fanout count or connected component type and size. After synthesis, a conventional place operation is performed on the logic circuit in operation 15 with local changes to the netlist (at only a chip primitive or cell or gate level) made in operation 17 to meet timing performance. A conventional routing operation is then performed in operation 19 in order to create a design of the circuitry in each of the ICs. If there are any unmet constraints, the process makes modifications with loop back iterations.
Formerly, when instance delays were dominant in the early synthesis tools, the timing estimates based on the statistical models were sufficiently accurate so that the separation of synthesis and placement required relatively few iterations back to the HDL and synthesis stages.
However, with shrinking technology nodes, the interconnect delays become significant, surpassing the gate delays. This results in the delay estimation in the synthesis operation becoming less and less correlated to the actual delays following placement and routing operations, leading to the lack of timing predictability between post-synthesis and post-layout results. Thus in many cases, after the placement and routing processes, the circuit physical layout cannot meet the circuit design criteria, and often the designers must start over from the synthesis step and repeat the synthesis/placement/routing processes.
To improve synthesis, it is important to account for the physical characteristics associated with the design (e.g. placement) during the synthesis process. A series of techniques have been adopted to bring placement information into the synthesis process such as floorplanning, in-place optimization (IPO), and physical synthesis.
In the floorplanning technique, the design is partitioned into regions on the chip and placement based interconnect estimation is used for inter-region interconnect, while interconnect within a region is estimated using statistical models. Floorplans can be used either at the early RTL stages or later after an initial synthesis run. Floorplanning can be extended to partitioning, replicating and slicing of RTL components into regions and combined with RTL level timing and area models. The improved timing from inter-region timing can then be used to more accurately drive RTL level optimizations. Producing a good quality floorplan manually is challenging and requires skilled users. Automatic floorplanners like the one from Tera Systems (U.S. Pat. Nos. 6,145,117 and 6,360,356) can create regions and assign RTL components to them. Because synthesis is decoupled and follows the automatic floorplanning, the accuracy of the timing and area information is poor during the floorplanning.
A technique called in-place optimization (IPO) provides back-annotation of place-and-route delays into the synthesis domain. Critical paths are re-optimized but because detail placement is not updated, interconnect delays for modified nets revert to statistical models. If many changes are made, then the following legalization of the resulting netlist may require moving instances far from their initial positions, resulting in large delay estimation errors. For this reason IPO is seen as unstable when significant changes are required to achieve timing closure.
Another technique is physical synthesis which is an improvement over the IPO technique where a small number of optimizations on a mapped netlist is interleaved with incremental re-legalization to maintain fidelity in the delay and resource metrics. A limitation of this technique is that individual changes are limited to modest increases in resources or the instability problem of the IPO technique re-surfaces. Currently there are several different algorithms for physical synthesis. FIG. 2 shows one algorithm providing a physical synthesis engine using timing estimations based on the proximity of placed instances. After the mapped netlist is initially placed in operation 23, the physical synthesis operation selects portions of the circuit for incremental optimization and re-placement in operation 24 which is performed only at the chip primitive level.
From the foregoing, it can be seen that algorithm improvements for electronic design automation are needed.
Prior patents also relate to or describe chip synthesis, and these patents include: U.S. Pat. Nos. 6,519,754; 6,711,729; 7,010,769; 6,145,117; and 6,360,356. Placement algorithms are recently described in a paper: Bo Hu, Timing-Driven Placement for Heterogeneous Field Programmable Gate Array, IEEE/ACM International Conference on Computer-Aided Design, November 2006 (ICCAD '06), pp. 383-388 (ISSN: 1092-3152; ISBN 1-59593-389-1).